package tulingxueyuan117;

import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2022/11/6 14:52
 * 快速升序排序（很重要）
 */
public class p36_希尔排序_912 {
    public static void main(String[] args) {
        int[] arr = {86,39,77,23,32,45,58,63,93,4,37,22};
        System.out.println(Arrays.toString(arr));
        System.out.println("=========================");
        int[] res = shellSort(arr);
        System.out.println("=========================");
        System.out.println(Arrays.toString(res));
    }

    public static int[] shellSort(int[] nums) {
        int len = nums.length;
        // 按增量分组后，每个分组中，temp代表当前待排序数据，该元素之前的元素均为被排序过的的
        // gap指用来分组的增量，会依次递减
        int currentValue, gap = len/2;
        while (gap>0){
            for(int i=gap; i<len; i++){
                currentValue = nums[i];
                // 组内已被排序数组的索引
                int preIndex = i - gap;
                // 在组内已被排序过数据中倒序寻找合适的位置，如果当前待排序数据比比较的元素药效，则将比较的元素在组内后移一位
                while (preIndex >= 0 && nums[preIndex] > currentValue){
                    nums[preIndex + gap] = nums[preIndex];
                    preIndex -= gap;
                }
                // while循环结束时，说明已经找到了当前待排序数据的合适位置，插入
                nums[preIndex + gap] = currentValue;
            }
            gap /= 2;
        }
        return nums;
    }
}
